package ljl.alg.wangzheng_camp.round1.bfsdfs;

import java.util.*;

public class _752_unlock {
    
    /**
     * 这可不是简单的 bfs 了，这是层序遍历！
     * */
    static class bfs {
        public int openLock(String[] deadends, String target) {
            if ("0000".equals(target)) return 0;
            Set<String> deadEndSet = new HashSet<>(Arrays.asList(deadends));
            if (deadEndSet.contains("0000")) return -1;
            LinkedList<String> q = new LinkedList<>();
            Set<String> seen = new HashSet<>();
            seen.add("0000");
            q.offer("0000");
            int step = 0;
            while (!q.isEmpty()) {
                step++;
                for (int i = 0, size = q.size(); i < size; i++) {
                    String cur = q.poll();
                    for (String move : nextMove(cur)) {
                        if (seen.contains(move) || deadEndSet.contains(move)) continue;
                        if (move.equals(target)) return step;
                        seen.add(move);
                        q.offer(move);
                    }
                }
            }
            return -1;
        }
        char prev(char c) {
            return c == '0' ? '9' : (char) (c - 1);
        }
        char next(char c) {
            return c == '9' ? '0' : (char) (c + 1);
        }
        List<String> nextMove(String cur) {
            List<String> res = new ArrayList<>();
            char[] arr = cur.toCharArray();
            for (int i = 0; i < 4; i++) {
                char c = arr[i];
                arr[i] = prev(c);
                res.add(new String(arr));
                arr[i] = next(c);
                res.add(new String(arr));
                arr[i] = c;
            }
            return res;
        }
    }
    
    static class a_star {
        public int openLock(String[] deadends, String target) {
            class AStar {
                final int steps, score;
                final String current;
                AStar(String current, String target, int steps) {
                    this.current = current;
                    this.steps = steps;
                    this.score = steps + getScore(current, target);
                }
                int getScore(String current, String target) {
                    int res = 0;
                    for (int i = 0; i < 4; i++) {
                        int dist = Math.abs(current.charAt(i) - target.charAt(i));
                        res += Math.min(dist, 10 - dist);
                    }
                    return res;
                }
            }
            if ("0000".equals(target)) return 0;
            Set<String> dead = new HashSet<>(Arrays.asList(deadends));
            if (dead.contains("0000")) return -1;
            PriorityQueue<AStar> q = new PriorityQueue<>(Comparator.comparingInt(a -> a.score));
            q.offer(new AStar("0000", target, 0));
            Set<String> seen = new HashSet<>();
            seen.add("0000");
            while (!q.isEmpty()) {
                AStar node = q.poll();
                for (String next : nextMove(node.current)) {
                    if (!seen.contains(next) && !dead.contains(next)) {
                        if (next.equals(target)) {
                            return node.steps + 1;
                        }
                        q.offer(new AStar(next, target, node.steps + 1));
                        seen.add(next);
                    }
                }
            }
            return -1;
        }
        char front(char c) {
            return c == '0' ? '9' : (char) (c - 1);
        }
        char back(char c) {
            return c == '9' ? '0' : (char) (c + 1);
        }
        List<String> nextMove(String cur) {
            List<String> res = new ArrayList<>();
            char[] arr = cur.toCharArray();
            for (int i = 0; i < 4; i++) {
                char c = arr[i];
                arr[i] = front(c);
                res.add(new String(arr));
                arr[i] = back(c);
                res.add(new String(arr));
                arr[i] = c;
            }
            return res;
        }
        
    }
}
